<![CDATA[
package examples;
import pizza.util.*;
]]><![CDATA[
class Tree<a> {
case Leaf(a elem);
case Branch(Tree<a> l, Tree<a> r);
}
]]><![CDATA[
class DelayedEnumerator<A> extends Enumerator<A> {
()->Enumerator<A> susp;
Enumerator<A> value = null;
public DelayedEnumerator(()->Enumerator<A> susp) {
this.susp = susp;
}
private Enumerator<A> force() {
if (value == null) value = susp();
return value;
}
public boolean hasMoreElements() {
return force().hasMoreElements();
}
public A nextElement() {
return force().nextElement();
}
}
]]><![CDATA[
class SameFringe{
static <A> Enumerator<A> fringe(Tree<A> t) {
return new DelayedEnumerator(
fun()->Enumerator<A> {
switch (t) {
case Leaf(A elem):
return new SingletonEnumerator(elem);
case Branch(Tree<A> l, Tree<A> r):
return fringe(l).concat(fringe(r));
}});
}
]]><![CDATA[
static <A extends Object> boolean sameFringe(Tree<A> t1, Tree<A> t2) {
Enumerator<A> fringe1 = fringe(t1);
Enumerator<A> fringe2 = fringe(t2);
while (fringe1.hasMoreElements() &&
fringe2.hasMoreElements() &&
fringe1.nextElement().equals(fringe2.nextElement()));
return !fringe1.hasMoreElements() && !fringe2.hasMoreElements();
}
static public void main(String[] argv) {
]]><![CDATA[
System.out.println(
sameFringe(
new Branch(
new Leaf("A"),
new Branch(new Leaf("B"), new Leaf("C"))),
new Branch(
new Branch(
new Leaf("A"), new Leaf("B")),
new Leaf("C"))));
]]><![CDATA[
System.out.println(
sameFringe(
new Branch(
new Leaf(new Integer(1)),
new Leaf(new Integer(2))),
new Leaf(new Integer(1))));
}
}
]]>